<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Transmission issues, encoding, and checksums',
	'<{subtitle}>' => 'Written in <span title="Communications and Networking">CS 2204</span> by <a href="https://y.st./">Alex Yst</a>, finalised on 2018-05-02',
	'<{copyright year}>' => '2018',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<h2>The hidden node problem</h2>
<p>
	Hidden nodes are nodes that share a wireless frequency, but are not within range of one another, and therefore are unable to detect one another (Dordal, 2014).
	The nodes are obviously hidden from one another, but that doesn&apos;t mean they&apos;re on mutually exclusive networks.
	A third node may be within range of both nodes, and thus subject to interference generated by the overlap of their ranges.
	In situations such as this, one node that&apos;s hidden from another may be transmitting, while the other node is about to transmit itself.
	The soon-to-be transmitting node listens to see if transmitting now will cause a collision, but being unable to hear the hidden node due to distance, it fails to detect the problem (Dordal, 2014).
	It begins its transmission, while the space occupying the overlapping transmission ranges experiences interference in the form of the mixed, now-garbled transmissions.
	Any nodes in that area won&apos;t be able to correctly decipher what either transmitting node is trying to say.
	Nodes within range of only one of the two transmitters won&apos;t experience the problem; the node out of range is hidden from such receivers, so from the receiver&apos;s perspective, it&apos;s as if the second transmission isn&apos;t occurring.
</p>
<p>
	For example, if A and B are too distant to hear one another, but close enough that their ranges overlap, they could both transmit.
	If node C is between the two, within that overlapped range, it&apos;ll only hear a garbled mess.
	However, if C is instead off to the side, only within range of A (or B, but not both), it&apos;ll hear A&apos;s transmission perfectly, but not B&apos;s at all (or if within B&apos;s range and not A&apos;s, it&apos;ll hear B&apos;s transmission perfectly but not A&apos;s).
</p>
<h2>Encoding</h2>
<p>
	We are asked to translate the &quot;3-byte $a[ASCII] string&quot; <code>Sun</code> into its 4B/5B encoding.
	True $a[ASCII] isn&apos;t actually used hardly anywhere, and characters in $a[ASCII] are only seven bits long, not the eight bits required to form a byte.
	This actually refers to the byte-long sequences in the &quot;$a[ASCII]&quot; section of Unicode.
	So first, we need to translate this into the binary encoding using a Unicode table.
	I happen to have a Unicode table application installed on my laptop, used both to look up information about characters and find symbols that are difficult to type so they can be pasted into documents.
	Using it, we find the characters <code>S</code>, <code>u</code>, and <code>n</code> are represented by the byte sequences <code>01010011</code>, <code>01110101</code>, and <code>01101110</code>.
	Remember that like all well-implemented things, the Unicode table is case-sensitive, so we need to take that into account when looking for the right character codes.
	From there, we can break the bytes into pairs of four-bit sequences: <code>0101</code>, <code>0011</code>, <code>0111</code>, <code>0101</code>, <code>0110</code>, and <code>1110</code>.
	Next, we use the encoding table provided by the textbook (Dordal, 2014) to translate each four-bit sequence into a five-bit sequence: <code>01011</code>, <code>10101</code>, <code>01111</code>, <code>01011</code>, <code>01110</code>, and <code>11100</code>.
	Lastly, we string all that together into one sequence: <code>010111010101111010110111011100</code>.
</p>
<h2>Internet checksums</h2>
<p>
	Our next exercise asks us to compute the Internet checksum of the three-byte message, <code>001100010011001000110011</code>.
	However, our textbook (Dordal, 2014) doesn&apos;t cover how to do that.
	The book says to take the one&apos;s compliment addition of all byte pairs to determine the checksum.
	(One&apos;s compliment is an outdated form of signed number representation; modern uses typically use the better-structured two&apos;s compliment, but the Internet is so old that it includes many older methods for legacy reasons.)
	However, what do you do if the bytes can&apos;t be paired up?
	That is to say, what do you do if there&apos;s an odd number of bytes, such as in the three-byte message this exercise specifies?
	Thankfully, the textbook isn&apos;t the document that defines the specification; it only tries to explain it.
	All we have to do is check out the authoritative document on the topic: in this case, $a[RFC] 1071.
	$a[RFC] 1071 (Braden, Borman, &amp; Partridge, 1988) says on page two that if an odd number of octets (8-bit bytes) is present, a zeroed-out octet is appended to the message before computing the checksum, giving us the even number of bytes we need.
</p>
<p>
	With all needed information now accounted for, we can begin computing our checksum.
	Our three-bit message is <code>001100010011001000110011</code>, so we break that into <code>0011000100110010</code> and <code>00110011</code>, then append <code>00000000</code> to the latter to get <code>0011000100110010</code> and <code>0011001100000000</code>.
	As the book says, we need to add these binary numbers together, check for overflow, and if overflow is present, add one to the result to convert the two&apos;s compliment form of the number into the one&apos;s compliment form.
	The process of adding binary numbers is beyond the scope of this assignment.
	You have ostensibly learned how to do that in a past course.
	You should have even built your own <a href="/en/coursework/CS1104/4-bit_arithmetic_logic_unit.xhtml">four-bit adder</a> in circuitry when you took <span title="Computer Systems">CS 1104</span>, meaning you should even understand how the process works in the computer mechanically.
</p>
<img src="/img/CC_BY-SA_4.0/y.st./coursework/CS1104/4-bit_adder.png" alt="4-bit adder" class="framed-centred-image" width="710" height="400"/>
<p>
	As such, I won&apos;t demonstrate the adding of the numbers bit by bit.
	Because both <code>0011000100110010</code> and <code>0011001100000000</code> begin in zeros and we&apos;re not adding more than these two numbers, we know there will be no overflow, so we won&apos;t need to account for such overflow by adding one at the end.
	All we have to do is add the two numbers, and we have our checksum: <code>0110010000110010</code>
</p>
<h2>Cyclical Redundancy Check</h2>
<p>
	$a[CRC] codes are supposedly computed based on the division of polynomials (Dordal, 2014), but for reasons you learned in <a href="/en/coursework/MATH1201" title="College Algebra">MATH 1201</a> (or <strong>*will*</strong>learn, depending on what order you&apos;re taking your courses in), the process is easily simplified into long division basic integers.
	The only difference between this and what we&apos;ve done in <span title="College Algebra">MATH 1201</span> is that in <span title="College Algebra">MATH 1201</span>, we worked in base ten, but now we&apos;re working in base two.
	The process itself is the same.
	The book tells us to find the so-called &quot;remainder&quot;, but there&apos;s no such thing.
	In division, we can have fractional parts.
	What we&apos;re really looking for is the result of <strong>*modulo division*</strong>, which is more comparable to what you have after overflow.
	For example, integer overflow in a computer, the fact that clocks repeat the same twenty-four (or twelve, depending on your clock) hours, and cycling back to zero on a kilometre-tracker on your motor vehicle are all forms of modulo-like overflow.
	You subtract all whole instances of the divisor and see where on the cycle your number is.
</p>
<p>
	We&apos;ve been asked to find the $a[CRC] checksum of the message <code>11011000</code> using the divisor <code>1011</code>.
	In other words, we need to find the value of <code>11011000</code> modulo <code>1011</code>.
	Long division typically gives us two numbers.
	The main number is the result of integer division.
	Integer division has no fractional components, as the result is restricted to be an integer.
	The result of integer division is the result of real division, but rounded down to the nearest integer.
	The result is always rounded down, never up.
	The second number is the result of modulo division; it&apos;s what most people mistake as a &quot;remaineder&quot;.
	This is the number we want when computing a $a[CRC] checksum.
	The long division for our problem looks like this:
</p>
<blockquote>
<pre>        10011
    ┌────────
1011│11011000
     1011
     ────
       10100
        1011
       ─────
        10010
         1011
        ─────
          111</pre>
</blockquote>
<p>
	As we can see, <code>11011000</code> modulo <code>1011</code> is <code>111</code>, so our $a[CRC] checksum is <code>111</code>.
</p>
<h2>Time-domain reflectometry</h2>
<p>
	We are asked what time domain-reflectometry is.
	This wasn&apos;t actually covered in the reading material for the week.
	However, Wikipedia comes to the rescue as it often does.
	It&apos;s a technique for measuring how energy waves get reflected back in physical transmission mediums such as wires (Wikipedia, 2017).
	While the book doesn&apos;t mention reflectometry in any way, it does mention the interference caused by reflected signals (Tanenbaum &amp; Wetherall, n.d.).
	It makes sense that we&apos;d want to measure such reflections, so we can attempt to reduce them.
</p>
<div class="APA_references">
	<h2>References:</h2>
	<p>
		Braden, R., Borman, D., &amp; Partridge, C. (1988, September). RFC 1071 - Computing the Internet checksum [Page 2]. Retrieved from <a href="https://tools.ietf.org/html/rfc1071#page-2"><code>https://tools.ietf.org/html/rfc1071#page-2</code></a>
	</p>
	<p>
		Dordal, P. L. (2014, April). 3.6.3 Hidden Nodes. Retrieved from <a href="https://intronetworks.cs.luc.edu/current/html/otherLANs.html#hidden-nodes"><code>https://intronetworks.cs.luc.edu/current/html/otherLANs.html#hidden-nodes</code></a>
	</p>
	<p>
		Dordal, P. L. (2014, April). 3.7.1.4 Hidden-Node Problem. Retrieved from <a href="https://intronetworks.cs.luc.edu/current/html/otherLANs.html#hidden"><code>https://intronetworks.cs.luc.edu/current/html/otherLANs.html#hidden</code></a>
	</p>
	<p>
		Dordal, P. L. (2014, April). 4.1.4 4B/5B. Retrieved from <a href="https://intronetworks.cs.luc.edu/current/html/links.html#b-5b"><code>https://intronetworks.cs.luc.edu/current/html/links.html#b-5b</code></a>
	</p>
	<p>
		Dordal, P. L. (2014, April). 5.4 Error Detection. Retrieved from <a href="https://intronetworks.cs.luc.edu/current/html/packets.html#error-detection"><code>https://intronetworks.cs.luc.edu/current/html/packets.html#error-detection</code></a>
	</p>
	<p>
		Dordal, P. L. (2014, April). 5.4.1 Cyclical Redundancy Check: CRC. Retrieved from <a href="https://intronetworks.cs.luc.edu/current/html/packets.html#cyclical-redundancy-check-crc"><code>https://intronetworks.cs.luc.edu/current/html/packets.html#cyclical-redundancy-check-crc</code></a>
	</p>
	<p>
		Tanenbaum, A. S., &amp; Wetherall, D. J. (n.d.). 2: The Physical Layer. Retrieved from <a href="https://my.uopeople.edu/pluginfile.php/268187/mod_book/chapter/150457/Chapter%202.pdf"><code>https://my.uopeople.edu/pluginfile.php/268187/mod_book/chapter/150457/Chapter%202.pdf</code></a>
	</p>
	<p>
		Wikipedia. (2017, December 3). Time-domain reflectometry. Retrieved from <a href="https://en.wikipedia.org/wiki/Time-domain_reflectometry"><code>https://en.wikipedia.org/wiki/Time-domain_reflectometry</code></a>
	</p>
</div>
END
);
